/*******************************************************************************
 * Copyright (c) 2010 Gregory Smith (gsmithfarmer@gmail.com).
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * 
 * Contributors:
 *     Gregory Smith (gsmithfarmer@gmail.com) - initial API and implementation
 ******************************************************************************/
/**
 * 
 */
package com.aslan.parser.infix;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Evaluate a postfix expression generated by {@link InfixParser}.
 * 
 * This class is an example of how an infix expression parsed by {@link InfixParser} can be
 * evaluated. Important characteristics of this evaluator include:
 * <UL>
 * <LI>The evaluator defines a large number of built-in functions (see {@link PostfixEvaluatorFunctions}. These functions
 * are available to all expressions evaluated by this class.
 * <LI>If an an expression contains a function THAT IS NOT DEFINED, the evaluator throw an Exception on evaluation.
 * <LI>If an expression contains an IDENTIFIER reference that is NOT DEFINED, the evaluator will assume that the
 * value of the variable is an empty string. Math operators interpret this as zero. 
 * <LI>New functions can be added using {@link PostfixEvaluator#addFunctions(Collection)} or {@link PostfixEvaluator#addFunction(IFunctionDef)}.
 * </UL>
 * <P>
 * This class is useful in a variety of situations. Examples include:
 * <UL>
 * <LI>Use an infix expression to filter  rows in a spreadsheet. The infix expression would include names
 * of columns in a spreadsheet and associated constraints. 
 * <blockquote>
	<pre>InfixParser parser = new InfixParser();
PostfixEvaluator evaluator = new PostfixEvaluator();

String constraint = &quot;MW &gt; 168 and MW &lt; 204.5 and CHEMIST='JOSIAH'&quot;;

IParsedExpression expr = parser.parse(constraint);

HashMap&lt;String, Object&gt; args = new HashMap&lt;String,Object&gt;();

for( ISpreadsheetRow row : spreadsheet ) {<
    args.put( &quot;MW&quot;, row.getValue(&quot;MW&quot;));
    args.put( &quot;CHEMIST&quot;, row.getValue(&quot;CHEMIST&quot;));
    boolean passFilter = evaluator.evalBoolean( expr, args );
    if( passFilter ) { // Do something }
}</pre>
</blockquote>

 * <LI>Use an infix expression to dynamically calculate values for an expression. Like the previous example,
 * variables can be used in the expression and bound at evaluation time.
<blockquote>
	<pre>
InfixParser parser = new InfixParser();
PostfixEvaluator evaluator = new PostfixEvaluator();

String constraint = &quot;(A+B)/23.0&quot;;

IParsedExpression expr = parser.parse(constraint);

HashMap&lt;String, Object&gt; args = new HashMap&lt;String,Object&gt;();

args.put(&quot;A&quot;, 123);
args.put(&quot;B&quot;, 452);
String answer = evaluator.eval(expr, args );
// Answer will be the result of (245+123)/23.0
</pre>

</blockquote>
 * </UL>
 * <P>
 * This class also has a large number of built-in functions (registered automatically when the class is
 * instantiated). Example usage in expressions:
 * <UL>
 * <LI>MIN( A, B, C) + 275
 * <LI>"Gregory is " + LENGTH( "Gregory") + " characters long"
 * </UL>
 * <P>
 * Additional function can be added via the {@link PostfixEvaluator#addFunction(IFunctionDef)} or
 * {@link PostfixEvaluator#addFunctions(Collection)} methods.
 * 
 * @author snort
 *
 */
public class PostfixEvaluator {

	private HashMap<String,IFunctionDef> functionMap = new HashMap<String, IFunctionDef>();
	private static final HashMap<String, Object> NO_VARIABLES = new HashMap<String,Object>();
	
	
	private class BooleanToken extends NumberToken implements IBooleanToken {
		public BooleanToken( boolean state ) {
			super( state?IBooleanToken.TRUE:IBooleanToken.FALSE);
		}
	}
	
	/**
	 * Create a new evaluator and install all of the functions defined in {@link PostfixEvaluatorFunctions}.
	 *
	 */
	public PostfixEvaluator() {
		addFunctions( PostfixEvaluatorFunctions.getInstance().getFunctions());
	}
	
	/**
	 * Convert any type of token to a number.
	 * 
	 * <UL>
	 * <LI>A number if simply returned.
	 * <LI>A empty string is treated as false.
	 * <LI>A non-empty string is parsed as a number (if possible).
	 * <LI>A non-empty non-number string is returned as true.
	 * 
	 * @param t token to convert
	 * @return token converted to a number type.
	 */
	private INumberToken getNumberFromToken( IValueToken t) {
		
		if( t instanceof INumberToken) {
			return (INumberToken)t;
		}
		
		String value = t.getValue();
		
		//
		// Treat empty strings or 0 and the "false" number.
		//
		if( value==null || value.length()==0 || "0".equals(value)) {
			return new NumberToken(IBooleanToken.FALSE);
		}
		
		//
		// Try to convert the token to a number.
		//
		try {
			double dd = Double.parseDouble(value);
			return new NumberToken(dd);
		} catch (NumberFormatException e ) {
			return new NumberToken( IBooleanToken.TRUE );
		}
	}
	
	public IBooleanToken getBooleanFromToken( IValueToken t ) {
		INumberToken n1 = getNumberFromToken(t);
		
		return new BooleanToken( n1.getInt()!= IBooleanToken.FALSE);
	}
	public void addFunctions( Collection<IFunctionDef> functionList ) {
		for( IFunctionDef f : functionList ) {
			addFunction(f);
		}
	}
	
	/**
	 * Add a new function definition to this evaluator.
	 * 
	 * 
	 * @param function add this function.
	 */
	public void addFunction( IFunctionDef function ) {
		functionMap.put( function.getName().toUpperCase(), function );
	}
	
	/**
	 * Remove a function defintion from this evaluator.
	 * 
	 * @param functionName remove this function (case does not matter).
	 */
	public void removeFunction( String functionName ) {
		functionMap.remove( functionName.toUpperCase());
	}
	
	/**
	 * Find the definition of a function by name (case does not matter).
	 * 
	 * @param name a function
	 * @return function definition if found, else null.
	 * 
	 */
	public IFunctionDef findFunction( String name ) {
		return functionMap.get( name.toUpperCase());
	}
	
	/**
	 * Evaluate a postfix expression and return the result.
	 * 
	 * This is NOT a good method to use if your expression contains user defined IDENTIFIERs. This method will
	 * treat all embedded identifiers as having empty string as their value. If your expression has identifiers,
	 * use a method like {@link #eval(IParsedExpression, Map)}.
	 * 
	 * @param expr an expression most likely generated via {@link InfixParser#parse(String)}
	 * @return result of evaluating the expression.
	 * 
	 * @throws Exception on any error (usually wrong number of arguments to a funcion or unknown function).
	 * 
	 * @see #eval(IParsedExpression, Map)
	 */
	public String eval( IParsedExpression expr ) throws Exception {
		return eval( expr, NO_VARIABLES );
	}
	
	/**
	 * Evaluate a postfix expression and return the result as true or false.
	 * 
	 * This method is a simple wrapper around {@link #evalBoolean(IParsedExpression, Map)} where no
	 * identifiers are defined.
	 * 
	 * @param expr an expression most likely generated via {@link InfixParser#parse(String)}
	 * @return result of evaluating the expression (true or false).
	 * @throws Exception on any error (usually wrong number of arguments to a funcion or unknown function).
	 */
	public boolean evalBoolean( IParsedExpression expr ) throws Exception {
		return evalBoolean( expr, NO_VARIABLES );
	}
	/**
	 * Evaluate a postfix expression and return the result as true or false.
	 * 
	 * For this method, false == (0, null, or a zero length string). This is the same criteria used by the
	 * built-in logic operators. All other values are interpreted as true.
	 * <P>
	 * Old C and C++ hacks should be pleased.
	 * 
	 * @param expr an expression most likely generated via {@link InfixParser#parse(String)}
	 * @param externalVariables mapping from identifiers in the expression to their value.
	 * 
	 * @return result of evaluating the expression (true or false).
	 * @throws Exception on any error (usually wrong number of arguments to a funcion or unknown function).
	 * 
	 *
	 */
	public boolean evalBoolean(IParsedExpression expr, Map<String, Object> externalVariables ) throws Exception {
		String answer = eval( expr, externalVariables );
		
		return !(answer == null || answer.length()==0 || "0".equals(answer));
	}
	
	/**
	 * Evaluate a postfix expression and return the result as a string.
	 * 
	 * This is the general method for evaluating an expression. Things you should worry about (also described in the class doc).
	 * <UL>
	 * <LI>Undefined functions will cause an exception.
	 * <LI>Undefined identifiers are treated as empty strings.
	 * </UL>
	 * 
	 * <P>
	 * The "externalVariables" structure maps identifiers that may appear in the expression to the values that should
	 * be used when evaluating the expression. Though any type of value can appear in the map, the following rules
	 * are used by the evaluator.
	 * <UL>
	 * <LI>null values are converted to an empty value (treated as an empty string, 0, or false depending on context)
	 * <LI>Boolean values are converted to 1 (true) or 0 (false).
	 * <LI>All other value types are converted using their toString() method.
	 * </UL>
	 * <P>
	 * In practice this works out well since a variable map usually contains String, Double, Integer, and Boolean data.
	 * 
	 * @param expr an expression most likely generated via {@link InfixParser#parse(String)}
	 * @param externalVariables mapping from identifiers in the expression to their value.
	 * 
	 * @return result of evaluating the expression (a String),
	 * @throws Exception on any error (usually wrong number of arguments to a funcion or unknown function).
	 */
	public String eval( IParsedExpression expr, Map<String, Object> externalVariables ) throws Exception {
		Stack<IValueToken> stack = new Stack<IValueToken>();
		HashMap<String, IValueToken> variables = new HashMap<String, IValueToken>();
		//
		// Convert the user supplied variables to tokens.
		//
		for( String key : externalVariables.keySet()) {
			Object obj = externalVariables.get(key);

			if( obj == null ) {
				variables.put( key.toUpperCase(), new StringToken(""));
			} else if( obj instanceof Boolean ) {
				variables.put(key.toUpperCase(), new BooleanToken( (Boolean)obj));
			} else if( obj instanceof Number ) {
				variables.put( key.toUpperCase(), new NumberToken(obj.toString()));
			} else if( obj instanceof String) {
				//
				// Look at the string and see if we can determine its syntax type.
				//
				String token = (String)obj;
				try {
					double dval = Double.parseDouble(token);
					variables.put(key.toUpperCase(), new NumberToken(dval));
					continue;
				} catch( NumberFormatException e ) {
					; // Ignore it
				}
				variables.put( key.toUpperCase(), new StringToken(token));
			} else {
				variables.put( key.toUpperCase(), new StringToken(obj.toString()));
			}
		}
		for( IToken token : expr.getPostfix() ) {
			switch( token.getType() ) {
			
			case STRING:
				stack.push( new StringToken(token.getName()));
				break;
				
			case NUMBER:
				stack.push( new NumberToken(token.getName()));
				break;
			
			case IDENTIFIER:
				IValueToken identifier = variables.get(token.getName().toUpperCase());
				
				if( identifier==null ) {
						stack.push( new StringToken("")); // No such identifier.
				} else {
						stack.push( identifier );
				}
				break;
			
			case FUNCTION:
			{
				IFunctionDef func = findFunction( token.getName());
				if( func == null ) {
					throw new Exception( "Function '" + token.getName() + "' is not defined");
				}
				IFunctionToken funcToken = (IFunctionToken)token;
				
				if( funcToken.getNArgs() < func.getMinArgs() ) {
					throw new Exception( "Too few arguments to function " + token.getName()
							+ " At least " + func.getMinArgs() + " are required");
				}
				if( funcToken.getNArgs() > func.getMaxArgs() ) {
					throw new Exception( "Too many arguments to function " + token.getName()
							+ " At most " + func.getMinArgs() + " are allowed");
				}
				
				IValueToken[] args = new IValueToken[funcToken.getNArgs()];
				
				for( int n = 0; n < args.length; n++ ) {
					args[args.length - n - 1] = stack.pop();
				}
				
				stack.push( func.eval(args));
				break;
			}
			
			case OP_UNARY_MINUS:
			{
				INumberToken n1 = getNumberFromToken(stack.pop());
				
				stack.push( new NumberToken( -1 * n1.getDouble() ));
				
				break;
		
			}
			case OP_EQ:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new BooleanToken(((INumberToken)v1).getDouble()==((INumberToken)v2).getDouble()));
				} else {
					stack.push( new BooleanToken(v1.getName().equals(v2.getName())));
				}
				break;
			}
			case OP_NOT_EQ:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new BooleanToken(((INumberToken)v1).getDouble()!=((INumberToken)v2).getDouble()));
				} else {
					stack.push( new BooleanToken(!v1.getName().equals(v2.getName())));
				}
				break;
			}
			case OP_GT:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new BooleanToken(((INumberToken)v1).getDouble()>((INumberToken)v2).getDouble()));
				} else {
					stack.push( new BooleanToken(v1.getName().compareTo(v2.getName())>0));
				}
				break;
			}
			case OP_LT:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new BooleanToken(((INumberToken)v1).getDouble()<((INumberToken)v2).getDouble()));
				} else {
					stack.push( new BooleanToken(v1.getName().compareTo(v2.getName())<0));
				}
				break;
			}
			case OP_GT_EQ:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new BooleanToken(((INumberToken)v1).getDouble()>=((INumberToken)v2).getDouble()));
				} else {
					stack.push( new BooleanToken(v1.getName().compareTo(v2.getName())>=0));
				}
				break;
			}
			case OP_LT_EQ:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new BooleanToken(((INumberToken)v1).getDouble()<=((INumberToken)v2).getDouble()));
				} else {
					stack.push( new BooleanToken(v1.getName().compareTo(v2.getName())<=0));
				}
				break;
			}
			//
			// Mathematical operators
			//
			case OP_MOD:
			{
				INumberToken n2 = getNumberFromToken(stack.pop());
				INumberToken n1 = getNumberFromToken(stack.pop());
				
				if( n2.getInt() == 0 ) {
					throw new Exception( "MOD of 0 is on defined");
				}
				
				stack.push( new NumberToken( n1.getInt() % n2.getInt()));
				break;
			}
			
			case OP_MULTIPLY:
			{
				INumberToken n2 = getNumberFromToken(stack.pop());
				INumberToken n1 = getNumberFromToken(stack.pop());
				
				stack.push( new NumberToken( n1.getDouble() * n2.getDouble()));
				break;
			}
			case OP_DIVIDE:
			{
				INumberToken n2 = getNumberFromToken(stack.pop());
				INumberToken n1 = getNumberFromToken(stack.pop());
				
				if( n2.getDouble() == 0.0 ) {
					throw new Exception( "Attempt to divide by zero");
				}
				stack.push( new NumberToken( n1.getDouble() / n2.getDouble()));
				break;
			}
			case OP_ADD:			// May also be string concatenation
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				if( v1 instanceof INumberToken && v2 instanceof INumberToken ) {
					stack.push( new NumberToken(((INumberToken)v1).getDouble()+((INumberToken)v2).getDouble()));
				} else {
					stack.push( new StringToken(v1.getValue() + v2.getValue()));
				}
				break;
			}
			case OP_SUBTRACT:
			{
				INumberToken n2 = getNumberFromToken(stack.pop());
				INumberToken n1 = getNumberFromToken(stack.pop());
				
				stack.push( new NumberToken( n1.getDouble() - n2.getDouble()));
				break;
			}
			//
			// Logical operators
			//
			case OP_NOT:
			{
				IBooleanToken b1 = getBooleanFromToken(stack.pop());
				
				stack.push( new BooleanToken(b1.getInt()==IBooleanToken.FALSE));
				
				break;
			}
			case OP_AND:
			{
				IBooleanToken b2 = getBooleanFromToken( stack.pop() );
				IBooleanToken b1 = getBooleanFromToken( stack.pop() );
				
				stack.push(new BooleanToken( b1.getInt()==IBooleanToken.TRUE && b2.getInt()==IBooleanToken.TRUE ));
				
				break;
			}
			case OP_OR:
			{
				IBooleanToken b2 = getBooleanFromToken( stack.pop() );
				IBooleanToken b1 = getBooleanFromToken( stack.pop() );
				
				stack.push(new BooleanToken( b1.getInt()==IBooleanToken.TRUE || b2.getInt()==IBooleanToken.TRUE ));
				
				break;
			}
			//
			// String operators
			//
			case OP_STARTS:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				stack.push( new BooleanToken(v1.getName().startsWith(v2.getName())));
				break;
			}
			case OP_ENDS:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				stack.push( new BooleanToken(v1.getName().endsWith(v2.getName())));
				break;
			}
			case OP_CONTAINS:
			{
				IValueToken v2 = stack.pop();
				IValueToken v1 = stack.pop();
				
				stack.push( new BooleanToken(v1.getName().contains(v2.getName())));
				break;
			}
			
			case OP_IN_LIST:
			{
				IListOperatorToken op = (IListOperatorToken)token;
				IToken d = stack.pop();
				String v = d.getName();
				stack.push( new BooleanToken(op.contains(v)));
				break;
			}

			//
			// Guard against a programmer adding a new token type
			// to IToken without adding it to this switch.
			// This code should not be covered by unit tests unless there is an
			// internal logical error in the package.
			default:
				throw new Exception( "Unrecognized token type " + token.getType() 
						+ ". Progammer failed to update PostFixEvaluator.parse() with new token type");
				
			}
		}
		return stack.peek().getValue();
	}
}
